/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/design-twitter
   @Language: C++
   @Datetime: 19-05-06 10:47
   */

/**
 * Definition of Tweet:
 * class Tweet {
 * public:
 *     int id;
 *     int user_id;
 *     String text;
 *     static Tweet create(int user_id, string tweet_text) {
 *         // This will create a new tweet object,
 *         // and auto fill id
 *     }
 * }
 */

#include<list>
class MiniTwitter {
	struct tweetqueue{
		bool operator()(const Tweet &a, const Tweet &b)const{
			return a.id>b.id;		// mini heap
		}
	};
	const static int tweetcount=10;
	unordered_map<int,std::list<Tweet> > tweets;	// user_id, tweets
	unordered_map<int,unordered_set<int> > follows;	// user_id, follows
public:
	MiniTwitter() {
		// do intialization if necessary
		tweets.clear();
		follows.clear();
	}

	/*
	 * @param user_id: An integer
	 * @param tweet_text: a string
	 * @return: a tweet
	 */
	Tweet postTweet(int user_id, string &tweet_text) {
		// write your code here
		Tweet t = Tweet::create(user_id, tweet_text);
		tweets[user_id].push_front(t);
		auto &v = tweets[user_id];
		if(v.size()>tweetcount) v.pop_back();
		return t;
	}

	/*
	 * @param user_id: An integer
	 * @return: a list of 10 new feeds recently and sort by timeline
	 */
	vector<Tweet> getNewsFeed(int user_id) {
		// write your code here
		priority_queue<Tweet,vector<Tweet>,tweetqueue> q;
		for(const auto &u:follows[user_id]){
			for(const auto &t:tweets[u]){
				q.push(t);
				if(q.size()>tweetcount) q.pop();
			}
		}
		for(const auto &t:tweets[user_id]){
			q.push(t);
			if(q.size()>tweetcount) q.pop();
		}
		vector<Tweet> vt;
		for(; q.size(); q.pop())
			vt.push_back(q.top());
		reverse(vt.begin(),vt.end());
		return vt;
	}

	/*
	 * @param user_id: An integer
	 * @return: a list of 10 new posts recently and sort by timeline
	 */
	vector<Tweet> getTimeline(int user_id) {
		// write your code here
		vector<Tweet> vt;
		for(const auto &t:tweets[user_id])
			vt.push_back(t);
		return vt;
	}

	/*
	 * @param from_user_id: An integer
	 * @param to_user_id: An integer
	 * @return: nothing
	 */
	void follow(int from_user_id, int to_user_id) {
		// write your code here
		follows[from_user_id].insert(to_user_id);
	}

	/*
	 * @param from_user_id: An integer
	 * @param to_user_id: An integer
	 * @return: nothing
	 */
	void unfollow(int from_user_id, int to_user_id) {
		// write your code here
		follows[from_user_id].erase(to_user_id);
	}
};
